Problem:
The Tower of Hanoi or Hanoi Tower, also called the Tower of Brahma, is an interesting mathematical puzzle game. It consist of 3 pegs, and any number of disks (usually around 3 to 8) with different sizes. The game starts with the disks in ascending order of size on a source (src) peg, the smallest at the top, to make a conical shape.

The objective of the game is to move all the disks from the inital position (usually a source (src) peg) to the destination (dst) peg, and the game play instructions are as the following:
1. Only 1 disk may be moved at a time.
2. No disk may be placed on top of a smaller disk.
3. Each move consists of taking the upper disk from a peg and slide it onto another peg, on top of the other disks that has already been present on that peg.

History:
The puzzle game was proposed by the French mathematician Edouard Lucas in 1883.
There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. It is not clear whether Lucas invented this legend or was inspired by it.
If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, it would take them 2⁶⁴-1 seconds or roughly 585 billion years; it would take 18,446,744,073,709,551,615 turns to finish.
(From Wikipedia: Tower of Hanoi)

Analysis:
The following shows the optimal solution of the game, and a way to determine the minimum number of steps it takes to move all the disks from initial position to another peg without placing a larger disk on top of a smaller one, where there is given 3 pegs and 1 with a set of n disks of increasing size.
To make use of D&C, only focus on the biggest disk around all the disks, initially all other n-1 disks are placed on the biggest one, so to move the biggest disk to the destination (dst) peg as the lowest disk, the only way is to move all other n-1 disks to the midway peg first, and after moving the biggest one to the destination (dst) peg, move the n-1 disks from the midway peg to the destination (dst) peg.
As described, such D&C idea makes the problem size to be reduced from n to n-1, so recursion may help us to solve the problem by the D&C approach.

Algorithm

The following shows the recursive solution in detail, given the pegs with labels A, B and C, or say "src", "midway" and "dst" in the following pseudo code respectively, and n number of disks with numbers from 1 (smallest, topmost) to n (largest, bottommost), to move n number of disks from peg A (src) to peg C (dst):

HANOI

The base case of the recursive algorithm occurs for n=1, and the step to move a single disk should be trivial.
Since the algorithm is optimal, the minimum number of steps for moving n disks will be T(n) = 1 + 2T(n-1). So the minimum number of steps is 1 + 2 + 2² + ... + 2^n-1 = 2ⁿ-1.

Time Complexity:
Since the minimum total number of steps is 2ⁿ-1, the time complexity is obviously O(2ⁿ)

Pseudo Code

  input: the number of disks (height), source peg name, midway peg name, destination peg name.
  output: the optimal solution of the Hanoi Tower.

HANOI( height, src, midway, dst ) {
      if( height > 0 ) {
          HANOI( height-1, src, dst, midway );
          println( "Step ", ++step, ": move disk ", height, " from peg ", src, " to peg ", dst );
          HANOI( height-1, midway, src, dst );
      }
  }

More about Time Complexity
Theoretically such D&C approach has already been optimal, however, some moves will be quite similar for some recursive steps (e.g. in the algorithm part, the moves in step 1 and 3 are similar), this phenomenon gives us a way to make use of the theory of dynamic programming to reduce the time complexity.

Try it yourself